1. Field of the Invention
This invention relates to an object search method and an object search system for use in three-dimensional image processing performed by a computer, and more particularly to a method for reading data satisfying a search condition from three-dimensional object data stored in a storage unit and to a system using the method.
2. Description of the Related Art
Various techniques have been proposed for processing a large amount of data in a limited memory. For example, in the world of computer graphics (CG), there are applications such as a driving simulation which requires the viewpoint to change frequently. Such applications store the three-dimensional coordinates of all objects, such as those of buildings or roads used in the simulation, in a large-volume auxiliary storage unit (hereafter called a storage unit) such as an external magnetic disk unit.
In most cases, the amount of data for these objects is too large to reside in a main memory in which simulation is executed. To solve this problem, a computer system uses virtual storage in which a large program or a large amount of data is divided into fixed-sized memory units called pages. These pages are brought into (page in) or out of (page out) memory as instructed by the operating system.
In computer graphics, processing called clipping is performed for rendering objects in a visual field. For example, when a distant view of a street is displayed on the screen, many objects such as buildings are shown. As the street is zoomed in, the number of objects shown on the screen is decreased. The visual field space is called a view volume. In other words, clipping divides the objects on the screen into two, visible parts and invisible parts depending upon whether or not they are within in the view volume, and then removes the invisible parts. This processing displays a smooth, natural image on the screen according to the eyepoint.
FIG. 1 shows a relation between the view volume and the objects. As shown in the figure, a view volume 2 is set up by such factors as the position of a eyepoint O, a line-of-sight vector V, the position of a front clipping plane 4, the position of a back clipping plane 6, a horizontal visual field angle, and a vertical visual field angle. The determination of the view volume is similar to selecting a container in which objects are contained. In FIG. 1, perspective projection is used to display a three-dimensional object on a two-dimensional screen. As a result, the view volume 2 is a truncated pyramid with the visual point O as the summit.
When the objects included in the view volume 2 are displayed, the view volume 2 is set up and, at the same time, object data is read. Because the amount of this data is large, as much of the object data as can be contained in main memory is loaded through the virtual storage feature and then the coordinates of the loaded object are transformed through viewing transformation. FIG. 1 shows two objects, 8 and 10, after coordinate transformation. Then, this object data is paged out, and the next data is paged in for which coordinate transformation is performed.
Next, clipping is performed. In FIG. 1, object 8, which is not contained in the view volume 2, is removed while object 10, which is contained in the view volume 2, is not. After clipping is performed on all objects in this manner, the objects contained in the view volume 2 in whole or in part are loaded into main memory again through the virtual storage feature for "rasterizing." Rasterizing, also called rendering, applies textures (patterns) or colors to the surfaces of the objects. Thus, necessary processing is performed only on necessary object data selected from a large mount of data to produce natural images.
However, the virtual storage feature, which divides data into pages of a predetermined size mechanically, sometimes divides data of one object into two pages as shown in FIG. 2. Processing of this object data requires two pages, meaning that if the object data is small but the page is large, a relatively large amount of data must be paged in and then paged out. In fact, the system is impractical for application, such as a driving simulation, in which data must be swapped frequently.